// 矩阵相关
// https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked
// 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
// 73. 矩阵置零
// TIP: 原地算法主要优化点在于利用某一行，列作为记录
// 一般算法考虑记录行或列的信息用来做标记处理
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let (mut rows, mut cols) = (
        std::collections::HashSet::<usize>::new(),
        std::collections::HashSet::<usize>::new(),
    );
    let (r, l) = (matrix.len(), matrix[0].len());
    for (i, v) in matrix.iter().enumerate() {
        for (j, &e) in v.iter().enumerate() {
            if e == 0 {
                rows.insert(i);
                cols.insert(j);
            }
        }
    }
    for e in rows {
        for ele in matrix[e].iter_mut() {
            *ele = 0;
        }
    }

    for e in cols {
        for i in 0..r {
            matrix[i][e] = 0;
        }
    }
}

#[test]
pub fn test_set_zeroes() {
    let mut vc = vec![vec![1, 1, 1], vec![1, 0, 1], vec![1, 1, 1]];
    set_zeroes(&mut vc);
    println!("{vc:?}",);
}

// https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked
// 48. 旋转图像
// 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
// 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
// TIP: 旋转等于对角交换+翻转
pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let len = matrix.len();
    for i in 0..len {
        for j in 0..(len - i) {
            let tmp = matrix[i][j];
            println!("{tmp}");
            matrix[i][j] = matrix[len - j - 1][len - i - 1];
            matrix[len - j - 1][len - i - 1] = tmp;
        }
    }

    for e in 0..len {
        for r in 0..len / 2 {
            let tmp = matrix[r][e];
            matrix[r][e] = matrix[len - r - 1][e];
            matrix[len - r - 1][e] = tmp;
        }
    }
}

#[test]
pub fn test_rotate() {
    let mut vc = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
    rotate(&mut vc);
    println!("{vc:?}",);
}

// https://leetcode.cn/problems/search-a-2d-matrix-ii/?envType=study-plan-v2&envId=top-100-liked
// 240. 搜索二维矩阵 II
// 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
// 每行的元素从左到右升序排列。
// 每列的元素从上到下升序排列。
// TIP: 经典T字形状
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let r = matrix.len();
    let c = matrix[0].len();
    let (mut a, mut b) = (0, c - 1);
    while a < r && b >= 0 {
        if matrix[a][b] == target {
            return true;
        } else if matrix[a][b] > target {
            b -= 1;
            if b==0 {
                return false;
            }
        } else {
            a += 1;
        }
    }

    false
}

#[test]
pub fn test_search_matrix() {
    println!(
        "{}",
        search_matrix(
            vec![
                vec![1, 4, 7, 11, 15],
                vec![2, 5, 8, 12, 19],
                vec![3, 6, 9, 16, 22],
                vec![10, 13, 14, 17, 24],
                vec![18, 21, 23, 26, 30]
            ],
            5
        )
    );
}
